Skip to main content

Full text of "BSTJ : The Construction of Missile Guidance Codes Resistant to Random Interference (Eckler, A.R.)"

See other formats


The Construction of Missile Guidance 
Codes Resistant to Random Interference 

By A. R. ECKLER 

(Manuscript received February 8, 1960) 

Many types of missiles are guided by a finite set of distinct commands 

radioed from the ground in the form of a time-sequence of rf pulses. The 
command information is contained in the n — 1 time spacings between 
successive pulses in a group of size n, and is encoded and decoded by means 
of muUiiapped delay lines combined with and gates. This paper discusses 
the problem of encoding command information (i.e., selecting the tim-e spac- 
ings between pulses) so that m false pulses (m ^ n — 2) cannot combine 
with the n true pulses in any way to form a false command. Although it is 
very easy to state the restrictions that must be imposed on the time spacings 
between the pulses in the different commands, no general methods exist for 
finding, among codes satisfying these restrictions, those codes in which the 
longest command is as short as possible. This paper presents certain lower 
hounds, together with a few empirically derived codes approaching these 
lower bounds. The relationship between these codes and the well-known 
error-correcting binary codes of information theory is discussed in an ap- 
pendix. 

I. INTRODUCTION 

Many types of missiles are guided by commands consisting of a time 
sequence of rf pulses. The missile receiver is capable of receiving not 
only the true command pulses, I)ut also any interfering rf pulses emanat- 
ing from other radars in the vicinity (friendly interference) or deliber- 
ately generated by the enemy (enemy interference). The purpose of 
this paper is to suggest command-encoding methods that minimize 
the effects of this interference. Greatest emphasis is placed on random 
interference models, because it is difficult to make realistic general as- 
sumptions about the behavior of an enemy \vh(t knows something about 
the code structure. 

The following sections may convey the impression that the construc- 

973 



974 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 

tion of a code invulnerable to random pulse interference is the only factor 
entering into the choice of a code. This is not meant to be the case; ac- 
curacy and reliability of decoding e(iuipnient, weight in the missile 
receiver, power considerations at the transmitter and missile dynamics 
and maneuverabihty also play very important roles. However, it will 
be made clear to the reader that code invulnerability should not be 
completely ignored, and that reas<)nai)le guideposts of dfesigii are avail- 
able. 

In order to fix ideas, the codes presented in this paper are discussed 
in terms of missile guidance. However, the reader will note that other 
applications are possible. In particular, the codes described here can be 
used in radio communications to provide protection against the mutual 
interference of many communications transmitters operating in the .same 
area on the same frequency. 

1.1 The Engineering Background of the Problem 

In many missile guidance systems, command information is sent to 
the missile by means of rf pulses. Specifically, the information is con- 
tained in the time spacings between successive pulses in a group of two 
or more pulses. Successive groups of pulses are spaced much more widely 
apart becau.sc of average power limitations on the magnetron. 

There are many physical devices suitable for encoding and decoding 
commands. This paper discusses a typical device for encoding discrete 
commands, such as "yaw left one unit" or "pitch down one unit." These 
commands are added up in the missile receiver until the desired correc- 
tion has been achieved. Discrete commands can also be used for such 
functions as turning rocket motors on or off or destroying the missile. 

A discrete command is conveniently decoded in the missile receiver 
by means of a lumped -parameter or distributed-parameter delay Hne 
tapped at several points (see Fig. 1). The earlier pulses in an incoming 
sequence are delayed the correct amounts by the delay line m order that 
the inputs to the and gate be simultaneously activated. 

In practice, it is sufficient that the several and gate inputs be activated 
within a short time interval. Let t denote the maximum possible range 
of input times (i.e., the difference in time between the earliest and latest 
input) that still activates the and gate. Because of r (which is called 
the discrete command tolerance), one must be careful not to let two 
distinct commands have similar encodings. It is shown hi the Appendix 
that an adeciuatc separation of different commands is always achieved if 
one assigns time spacings in integral multiples of the discrete command 
tolerance t. 



MISSILE GUIDANCE CODES 
DELAY LINE OF MISSILE RECEIVER 



975 



INCOMING 
PULSES 



- t, - 



YAW-LEFT DISCRETE 
COMMAND ENCODED AS 



\i±A 



PITCH-DOWN DISCRETE 
COMMAND ENCODED AS 



A 



Fig. 1 — Method of decoding discrete command by means of distributed- 
parameter delay line tapped at several points. 

It is clear that only t wo pulses arc needed to encode a command. How- 
ever, in order to obtain a greater degree of security against false pulses, 
it is necessary to use three or more pulses per command. The mathe- 
matical problem discussed in this paper is the construction of such 
security codes. 

The same delay line and and gate can be used in the communications 
problem already menlioned. Here the group of pulses plays the role of 
an address code rather than a command. Each communications trans- 
mitter uses a specific address code as a generalized "pulse" with which 
to communicate information; thus, different transmitters can use the 
same frequency witliout interfering with each other. 

1.2 A Criterion for Judging Code Effectiveness 

The invulnerability of codes to false pulses is measured by the follow- 
ing simple criterion : the maximum number of false pulses that cannot 
interfere with a code group (either by changing the position of a com- 
mand or producing a diiTerent conmiand), no matter how these false 
pulses are placed in time with respect to the true code group. 

This criterion permits only a rough ordering of codes with respect to 
invuhierability ; redundancy of orders and clo.sed-loop missile response 
also play an obvious role. However, it does focus attention on a very 
important factor. No matter what random interfeience model is postu- 
jated — for example, a PoLsson process of random pulses, a set of radars 
with approximately the same pulse repetition frequency operating inde- 



976 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 

pendently of each other, or peaks of random gaussian noise having aver- 
age po\vcr a certain number of decibels Ijclow the pulse recognition 

threshold — false single pulses per unit time are much more frequent 
than false pairs having a particular spacing, false pairs are much more 
frequent than false triples, and so on. This situation is especially true 
when the discrete command tolerance t is small with respect to the 
average time between false pulses. 

II. ONE-STAGE CODES 

This section discusses the problem of constructing one-stage codes 
(that is, codes using a delay line and and circuit) for a set of k distinct 
commands. Each encoded command consists of a sot of n pulses; the 
command information is contained in the (n — 1) time spacings between 
pairs of successive pulses. One can encode these /.■ commands such that 
i false pulses cannot combine m any way with (n — i) pulses from any 
command to form either the same command (shifted in time) or one of 
the other (k -~ 1) commands. The maximum possible value of i is equal 
to (n — 2), because (n — 1) false pulses can combine with one ti-ue 
pulse to form false commands in many different ways. 

We first discuss methods of encoding commands invulnerable to 
(n — 2) false pulses; later this restriction is relaxed to fewer pulses. 

2.1 The Construction of One-Stage Codes with Maximum Protection 

It may be helpful to think about a specific coding problem while 
reading this section. Let us assume that we wish to encode two commands 
(k = 2) consistuig of three pulses each (n = 3); by suitable encoding 
we can insure that a single false pulse {n — 2 = 1 ) cannot combine with 
two pulses to form any false command. This example will be referred to 
below by sentences enclosed in brackets. 

As mentioned earlier, it is convenient to make all the time spacings 
of a discrete code integral multiples of the discrete command tolerance 
T, in order to avoid overlapping problems between different commands. 
This being so, one can represent the various time spacings with the in- 
tegers 1, 2, 3, ■ • ■ ; thej'th n-pulse command is represented by an (n — 1)- 
dimensional vector of integers (ii, t'^, ■ ■ ■, t^-x). [Specifically, the first 
command is given by the pair of integers {t\, ti) and the second com- 
mand by ((i^, ^2^^)]. 

The one-stage coding problem for discrete commands can now be 
stated in mathematical terms. Assume that one has k distinct n-pulse 
commands. All these commands are effective against {n — 2) false 
pulses [in the sense discussed above] if and only if the following 
kn{n — l)/2 integers are all different: 



MISSILE GUIDANCE CODES 977 

t/ fori = 1, 2, -■ ■, n - 1 undj = 1, 2, •■ ■, t; 

ti' + ti+i.' iovi = 1,2, • • • , 71 - 2 and ;" - 1,2, • ■ ■ , A:; 



i;«/ forj= 1,2, •■■,k. 

[In our specific problem, we require that the six integers fi\ k , h + (■• , 
(}', ti, k' + t2^ all be different.] 

The theorem can I)c proved by indirect reasoning. Suppose that 
(n — 2) false pulses have combined with two true pulses to form a false 
command. Then the spacing to between the two true pulses must be 
equal to more than one of the Jai(n - l)/2 integers listed above (the 
set of all possible spacings between pairs of pulses in the k commands). 
Fcr, if (o were equal to only one of these integers, the only command 
that could be foimed with the aid of these two true pulses would be the 
correct command. Conversely, if two of these integers are the same, it is 
easy to construct a false command using (n - 2) properly spaced false 
pulses. [For example, if the two commands are (3, 8) and (2, 6), then 
the second command can be falsely formed from the first command by 
placing an extra pulse two time units after the second pulse in the first 
command. In this case, the six integers are 3, 8, 11, 2, 6, 8, and h is 

equal to 8.] 

If one allows the integers t/ to be arbitrarily large, there is no diffi- 
culty in discovermg suitable codes. [For example, (31, 73) and (9, 45).] 
However, equipment and time restrictions usually make it desnable to 
keep all the commands as short as possible (measured from first to last 
pulse). Therefore, one may pose the following interesting mathematical 
problems : 

i. For a given /: and n, what is the minimum possible length of the 
longest command under the restrictions above? 

ii. Are there any (simple and practical) methods for constructing 
codes w^ith minimum command length (or a little longer)? 

Neither of the above two problems has been solved; lower bounds can 
(in a limited way) be set for the first, and the second has largely been 
investigated by trial and error. The problem is similar to the eight 
queens problem* in chess, but with additional restrictions. More gener- 



* The eight queens problem consists of placing eight queens on the chess board 
BO that no queen can capture any other along a row, column, or diagonal. A specific 
Code can be characterized by a pair of integers {a, b) ; this denotes a position on a 
generalized chessboard (not restricted to the eight-by-eight size). 



978 THIO HELL SYHTKM TECHNICAL JOUKNAL, JULY 1 9()0 

ally, it appears to be a problem in partitions in the theory of num- 
bers. 

A general lower bound L for the minimum possible length of the long- 
est command is given by kn{n — l)/2. However, this bound cannot 
always be achieved even for three-pulse codes. For a three-pulse code, 
it is true that 

If the longest command length is equal to Zk^ the set of mtegcrs 

tj(i = 1, 2;j ^ 1, 2, . ■ ., k), h' + tAj = 1,2, ■■■, k) 

is a rearrangement of the set of integers (1, 2, ■ ■ •, 3/i;). Therefore, the 
sum of the two sides of the above equation is 3A(3/.; + l)/2, and the 
sum of one side alone is 3/r(3/v + l)/4. But this last quantily is an 
integer if and only if ^: = (mod 4) or k = 1 (mod 4). In other words, 
'6k is a lower bound L when k = 1, 4, 5, 8, 9, 12, 13, - ■ ■, and Sk + 1 
is a lower bound L for all other k. 

2.2 Some Typical One-Stage Encodings 

We now list specific discrete encodings for .several values of /: and n. 
For the three-pulse codes the lower bound L for the longest delay line 
needed has actually been achieved for k = 1 (1) 10. The first number 
gives the time .spacing between the first and second pulses, and the 
second number the time spacing between the second and third pulses: 

Typical minimum-length discrete- command three-pulse encoding.s 

(1.5) (3,4) 

(4.6) (1,7) (2,3) 
(1,9) (3,8) (5,7) (2,4) 

(3,12) (5,9) (2,11) (4,6) (1,7) 

(4,15) (2,16) (5,12) (3,8) (1,9) (6,7) 

(3,19) (5,16) (7,13) (6,12) (2,15) (4,10) (1,8) 

(1,23) (2,11) (3,18) (4,10) (5,15) (6,16) (7,12) (8,9) 

a, 26) (3,22) (9,15) (2,21) (6,14) (7,12) (10,8) (4,13) (5,11) 

(5,26) (14,16) (2,27) (8,20) (4,21) (9,15) (1,22) (7,12) (3,10) (6,11) 

Undoubtedly this list could be indefinitely extended, since it is easy to 
discover many different encodings for any k which have the same length 
for a maximum -length command. 

Unfortunately, an analogous method for impnmng the lower bound 
L does not exist for n > 3. As n increases, it becomes more difficult to 
keep the minimum delay line small, and kn(n — l)/2 becomes a very 
unrealistic lower bound. 



k 


L 


2 


7 


3 


U) 


4 


12 


5 


15 


6 


19 


7 


22 


8 


24 


9 


27 


10 


31 



MISSILE (.;ril)AXCE CODMR 



1)79 



The tables below list representative discrete-command four-, five- and 
six -pulse encodings; the reader is invited to find an encoding with a 
smaller L' if he can {U denotes the minimum command length that has 
been achieved, but it may not be the true minimum) : 

Typical discrete-command four-pulse encodings 



A; 


L 


L' 


2 


12 


13 


3 


18 


21 


4 


24 


27 


5 


30 


31 



(2,5,6) (3,1,8) 

(1,5,12) (2,8,11) (3,4,9) 

(1,11,15) (2,6,17) (3,7,14) (4,5,13) 

(2,20,9) (3,14,13) (4,8,16) (5,10,11) 



(6,1,18) 



k 


L 


L' 


Typical diacrete-command five-pulse encodings 


2 

3 


20 
30 


25 

38 


(1,8,3,13) (2,5,10,4) 
(1,5,12,20) (2,8,11,14) (3,4,9,15) 



30 



45 



Typical discrete-command six-pulse encodings 



(1,8,3,13,20) 



(2,5,10,4,18) 



If encodings not given in these tables are desired, it should be possible 
to use a high-speed digital computer to search through a large number 
of encodings (either systematically or at random) and print out the 
minimum-length encoduig that it tmds. Unless an algorithm for comput- 
ing encodings is found, this is the only practical method available. 

2.3 A General Class of Discrete Codes 

As noted hi Section 2.2, the length of the longest conmiand ui- 
creases rapidly with n, the number of pulses in the command. This, of 

course, is the price that one pays for protecting oneself against (n — 2) 
false pulses aiTanged in any pattei'n whatever. One can always reduce 
the code length by i-educing the protection; that is, construct minimum- 
length n-pulsc codes that protect against (« — 1) or fewer pulses (i = 
3, 4, 5, ■ ■ •, n — 1). The following formulation of the problem is more 
realistic. Suppose that one wishes protection against 7n false pulses com- 
bining with (n — m) pulses in any command. 

i. IIow does one construct H-pulse codes [n > m + 2), keeping the 
length L of the longest command as short as possible? 

ii. If power is no limitation (any n can be used within reason), for 
what value of n is L minimized? 

No general solution to either of these proljlems is known. This section 
presents typical encodings for a few of the simplest codes, which were 
found by trial-and-error methods. 

The simplest problem in this class is the construction of a four-pulse 



980 



THE BKLL SYSTEM TECHNICAL JOUKNAL, JULY 1900 



code invulnerable to a single false pulse. It can be proved (by the method 
used in Section 2.2) that, in order for a four-pulse, A;-command code to 
be invulnerable to one false pulse the following 4/v- integer-pairs must all 
be different: 

forj = 1, 2, •■■,k. 

As before, a lower bound L for the length of the longest command can 
be obtained. There is one integer -pair (1,1) which sums to 2; there are 
two more which sum to 3, and in general there are n(n — l)/2 with sums 
less than or equal to n. Therefore, a lower bound L is given by the smallest 
value of n satisfying 4A ^ n(n — l)/2. Most of the specific discrete 
encodings listed below actually achieve this bound; the ones that exceed 
it by one are marked with an asterisk : 

k L Typical four-pulae encodings invulnerable to one false pulae 



a, 1,2) 
(1,3,1) 
(4,1,1) 
(1,4,2) 

(1,3,1) 
(1,6,2) 
(1,5,3) 



(2,1,2) 

(1,2,2) 
(2,4,1) 
(3,2,3) 
(2,5,1) 
(2,2,5) 



(2,1,3) 

(1,1,2) 
(4,2,1) 
(1,2,4) 
(3,3,2) 



(3,2,1) 
(1,2,4) 
(4,2,1) 
(4,2,1) 



(2,5,1)* 

(3,2,3) 

(7,1,1) 



(1,3,1) 
(1,3,4) 



(2,3,1)* 



For moderate values of k, the minimum length has been reduced more 
than 50 per cent by adding one more pulse to the code. 

In order to construct a five-pulse /c-command code that is invulnerable 
to two false pulses, it can be shown (by the method used in Section 2.2) 

that the following Wk integer-pairs must all be different: 

(h^h'), {tJ,tJ), (V,//), 

ik' + k', k'), ik' + h\ U'), {h\ k' + V), (k\ k' + ti), 

{k\ k' + k' + U'), (k' + k\ k' + k'), ik' + k' + k\ k') 

iovj = 1,2, ■■',k. 

The lower bound L is given by the smallest value of n satisfying lO/c ^ 
n{n — 1 ) /2. Three typical encodings are given below ; it it believed that 
they are the shortest ones possible : 

Typical five-pulae encodings invulnerable to two false pulses 



(1,2,2,1) 
(2,3,1,2) 
(3,3,1,4) 



(1,3.4,1) 
(2,2,1,6) 



(1,7,1,2) 



MISSILE GUIDANCE CODES 



981 



In order to construct a five-pulse fc-command code that is invulnerable 
to one false pulse, it can be shown that the following 5k integer-triples 
must all be different: 

(ti, W, h'), (M , is , U ), 

(// + k\ h\ tj), {k\ uj + h\ u'), (A\ t,\ tj + (/■) 

for J = 1,2, ••■,1: 

The lower bound L is given by the smallest value of n satisfying bk ^ 
n{n — l)(n - 2)/6. A few typical encodings (believed to be minimum 
length) are given below: 

it L Typical five-pulse eocodings invulnerable to one false pulse 



(1,1,2,1) 
(1,1,3.1) 
(1,1,3,1) 
(1,1,3,1) 



(2,1,1,2) 
(2,1,1,2) 
(2,1,1,2) 



(1,3,2,1) 
(1,3,2,1) 



(2,2,1,2) 



As mentioned before, these tables can be extended with the aid of a 
high-speed digital computer. 

The following table summarizes the known behavior of one-stage dis- 
crete-command codes. It records the shortest known length of the long- 
est command ; most of these lengths are believed to be the smallest ones 
achievable. It is evident that one can often reduce this length quite 
markedly by adding pulses to the code, and that the savings are likely 
to be greater as the number of commands increases: 



Codes Invuloerable to 
One False Pulse 



Codes Invulnerable to 

Two False Pulses 





Numbe 


r of pulses 


k 


3 


4 5 


1 
2 
3 
4 
5 
6 


3 
7 
10 
12 
15 
19 


4 5 

5 6 

6 7 

7 7 

8 — 
8 — 





Number of pulses 


k 


4 


5 6 


1 
2 
3 
4 


7 
13 
21 
27 


6 — 
9 — 

11 — 



III, TWO-STAGE CODES 

The single-stage codes discussed in Section II should prove quite use- 
ful to the designer of missile guidance equipment. However, they suffer 
from the drawback of trying to do too many things at once. Sometimes 
it is more reasonable 1o lireak the decoding job up into several smaller 
jobs that are performed in sequence. Thus, the output puise resulting 



982 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 

from one decoding operation becomes an input pulse to the next decoding 
operation. 

An important advantage of such a break-up is that at least part of 
the security function of the code can be separated from the command 
function. This means that one can build in between-missile security 
without behig forced to change the command codes from one missile to 
the next. Furthermore, the between-missile security codes can be used 
to mcrease the search time of a knowlcdgealile enemy for the correct 
code. 

A second advantage is greater simplicity of both codes and compo- 
nents. If one needs to protect against (say) as many as four false pulses, 
it is not easy to find optimum single-stage codes, and the required de- 
lay lines may not be available. Multistage codes provide additional 
designs that may be easier to instrument. Balanced against this, of 
course, may be an increase in the number of components needed. 

Multistage discrete-command codes are those that use a delay line 
and multiple .\nd circuit decoding mechanism (see Section I) at each 
stage. For simplicity, let us restrict ourselves to two-stage codes, which 
possess most of the potential advantages of multistage codes. Let the 
symbol i \ j denote a two-stage code containing ij pulses : the first stage 
decodes j' clusters of i pulses each and the second stage decodes the cluster 
of J output pulses emitted by the first-stage and circuit. 

Usually the command part of the code occurs at the second stage. 
However, it makes no difference whatever which stage it is assigned to: 
an i \ j security-command code has precisely the same invulnerability 
to false pulses as does a j | i ecmimand-security code. Let us assume for 
convenience that the commands are always contained in the second 
stage. 

3.1 An Upper Bound for the Protection 

How much protection can an i \ j code give against false pulses? As- 
.sume that the two stages are each designed according to single-stage 
rules, so that they are in\'uhierab]e to (i — 2) and (j — 2) false pulses, 
respectively. Then an upper bound to the inmiber of false pulses that 
can be arranged in any pattern whatever with the ij true pulses wilh- 
out forming a false (or repeated) command is 

M = mm [i(j - 1) - l,j(i - 1) - 1]. 

The first term arises because false pulses can be arranged in (,/ — 1) 
groups of i false pulses each, and these gi'oups can be combined with one 
true i-pulse group to form a false command. The second term arises 



MISSILE GUIDANCE CODES 983 

JJ I I I I 



TYPICAL ENCODING 



u 



FIRST-TERM ERROR 
. Lfj-1)-1 = 3 



J_i_L 



SECOND-TERM ERROR 



Fig. 2 — Firat- and second-term error for 2 | 3 code. 

because false pulses can be arranged in j groups of (i — 1) false pulses 
each, augmented by j true pulses, one from each of the .7 groups in the 
correct code. This is illustrated in Fig. 2 for the 2 j 3 code. 

Although M is the same for lioth an i \ j and aj\i code, the two er- 
rors are not symmetric. Note that the first type of error can result in a 
false command, but the second type of error can only repeat the sarne 
command slightly earlier or later in time. The second error is likely to 
be less serious, and in fact can be eliminated by introducing a device 
that prevents repetition of the same command within a specified period 
of time. Accordingly, in the rest of this section we emphasize codes that 
are protected against i(j - 1) - 1 false pulses combming with true 
pulses to form a different false command. 

For i, j greater than or equal to two, the maximum possible protec- 
tion is always less than that achievable with a smgle-stage code using 
ij pulses. Thus, these codes are somewhat comparable to the reduced- 
protection shigle-stage codes discussed in Section II. 

3.2 Methods for Combining Securitij and Command Codes 

In order to actually achieve the upper bound of the protection, one 
must be a little careful when combining the two .stages of the code. 
There are many ways of doing this, and the choice of a particular method 
depends upon the ease of instrumentation. For example, consider the 
following alternatives for the 2 ) 3 code (see Fig. 3). 

3.2.1 Short Command Codes, Long Security Codes 

Let the three-pulse commands be encoded according to the methods 
in Section II. The longest command will be approximately Sk if there are 
k different commands. The two pulses forming the security code should 
bo more than Qk apart in order to avoid the possibility of three false 
pulses forming a false command. This design is probably the easiest to 
instrument. 



984 



THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 

_.- COMMAND ENCODING -^^ 

v^^ — I r — t 1 

I I I I I I 



(a) 



SECURITY ENCODING 



COMMAND ENCODING 



(b) [ 



I I I L4 



SECURITY ENCODING 



COMMAND ENCODING 



Ccj 



JJ u 



u 



SECURITY ENCODING 



Fig. 3 — Methods for combining security and command codes: (a) short com- 
mand codes, long security codes: (b) interleaved security and command codes; 
(c) long command codes, short security codes. 

3.2.2 Interleaved Security and Command Codes 

Let the spacing between the two-pulse security codes consist of odd 
integers, and encode the three-pulse commands in even integers using 
the methods discussed in Section II. To iUustrate: if four commands are 
to be sent, let them be (2, 18), {6, 16), (10, 14) and (4, 8). More se- 
curity and command codes can be ea-sily added. 

3.2.3 Long Command Codes, Short Security Codes 

Let the spacing between the two-pulse security codes be given by the 
integers 1, 2, ■ ■ ■ , m. Encode the three-pulse commands in multiples of 
2m (or greater) according to the methods of Section 11. This is likely 
to be the most difficult design to instrument. 



These alternatives all provide the maximum possible protection ; four 
false pulses are needed to form a false command, and three false pulses 
are needed to shift the true command in time. 

The first and third alternatives are very easy to encode for any values 
of i and J (if the necessary single-stage codes are available), and are not 
discussed further. False pulses that combine with true pulses to form false 



MISSILE GUIDANCE CODES 985 

security codes cannot possibly form false commands as well, because 
these false pidses are either too far from or too close to the other true 
pulses to do the job. Fretiueiitly the longest delay line is somewhat longer 
for these alternatives than it would be if an interleaved code were used. 
Accordingly, we devote the rest of this part of the paper to the construc- 
tion of interleaved codes. 

3.3 The Problem of Interleaving Security and Command Codes 

This section discusses the prol)lem of interleaving z-pulse security 
codes with ^-pidse command codes in such a way that one is protected 
again.st i(j - 1) - 1 ftilse pulses forming a false command. Probably 
the simplest way to interleave the codes is to reserve the integers /(i), 
2f(i), 3/(i), ■ ■ ■ for the command codes. Then one can coJistruct mini- 
mum-length command codes uivulnerable to (j - 2) false input pulses 
according to the methods discussed in Section II. [It will be shown later 
that the minimum possible value for/(0 is i.] 

The interleaving problem is now reduced to the problem of selecting 
the security code spacings so that one is protected against i(j - 1) - 1 
false pulses. The following sections present two restrictions on the secu- 
rity codes and show that these restrictions are sufficient to guarantee this 
protection. No claim is made that this is the only way to interleave 
codes; however, the resulting codes do have optimum properties, which 
are described later. 

3.3.1 Two Restrictions on the Security Code 

The security code spacings (ti,t2, ■■• ■ ^-i) should be chosen in such 
a way that 

(a) no set of (i - 2) false pulses can combine with two true pulses 

to form a false security code, and 

(b) none of the i{i - 1) integers 

±tk, k = 1,2, ■■■ ,i - I; 

Mtk + h+i), k = \,2, ■■- ,i-2; 



±{ti + t2+ ■•■ + /.■-!) 

should be a multiple of /(i) [that is, equal to mod/(0]. 

The first restriction states that security codes should be single-stage 
codes consisting of only one command (see Section II). The second re- 
striction accomplishes two goals. Fh-st, since none of the integers h , 



986 THE BELL SYSTEM TECHNICAL JOURNAL, JULY I9G0 

t t _|J U L i i II |- 't.-t.) 

^^ I I i i j i i I I L = 

i I 

t _LLi U UJ LL t. 



Fig. 4 — Six false security codes for a three-pulse code. 

ti -\- t-i , • ■ • , ii + t-> -\- ' ■ ■ -\- ti-i is a multiple of /(i), any i \ j code will 
consist of the full set of ij pulses. (Any pulse serving two functions at 
the same time is a natural candidate for a false pulse.) Second, the above 
set of mtegers lists the starting times of all the false security codes con- 
sisting of (i — 1) false pulses and one true pulse (relative to the starting 
time of the true security code). For example, for a three-pulse security 
code, the six false security codes are shown in Fig. 4. 

Now, consider what happens if one of the above spacings is a multiple 
oif(i). One of the command code spacings is formed by the false security 
code corresponding to this spacing and one of the true security codes; 
the other (j — 2) command spacings are formed by i(j — 2) false pulses. 
But (i — 1) + i(j — 2) ^ i(j — 1) — 1, which is the number of false 
pulses we wish to protect against. The 3 | 4 code illustrates this point 
(see Fig. 5). 

It is shown in Section 3.3.2 that codes .satisfying these restrictions are 
protected against i(j — 1 ) — 1 false pulses, and that the mmimum possi- 
ble value oi f(i) is i. 

3.3.2 Proof That These Restrictions Insure Protection 

Given these two restrictions, how can false commands be formed? 
Each security code in the false command can include at most one true 



TRUE 
CODE 



FALSE 
CODE 



I II I II LU LLL 

I ■■III ■■■ ■■■ 

■■III ■■■ ■■■ 

■■III ■■■ ■■■ 

■ ■ I i_i ■ ■_■ J — ■ ■ 

k *~ ALL COMMAND CODE SPACINGS 

ft, +13) = A MULTIPLE OF f(0 IN BOTH COOES 

^ ' 2' ^ ^ ARE MULTIPLES OF f(L) 

Pig. 5 — A 3 I 4 code with spacing a multiple of /(t). 



MISSILE GUIDANCE CODES 987 

pulse, because of restrictions (a) and (b). [There is one exception: a 
false command can be constructed out of one true security code and 
(j - I) false security codes of i pulses each.] Furthermore, ij pulses are 
needed for the false command, according to restriction (b). Therefore, 
if we can show that the false command contains at most i true pulses 
(one in each of i different false security codes), then we are done, for the 
(ij _ {) or more false pulses needed to make up the balance of the false 
command will exceed i(j - 1 ) - 1, the number of false pulses we wish 
to protect agamst. Since all the true command spacings are multiples 
of /(z), it is sufficient to show that one can select at most i false security 
codes consisting of one true pulse and (i - 1 ) false pulses each, which 
arc all spaced f(i) apart from each other. 

In the preceding section, we listed all the i(i - 1) possible false se- 
curity code startmg times (relative to the true security code). If we can 
show that exactly i of these times are equal to a (mod i), where a = I, 
2^ ... ^ i — 1, then we will have proved that at most i different false 
security codes can have the proper command spacing. Furthermore, we 
will have proved that/(0 = i; and it is clear that this is the smallest 
integer it can be. 

Consider the following arrangement of the i{i - 1) false security 
code starting times in a matrix with i rows and (i — 1) columns: 

h,h-\- t2,h^ t2-\- h, , /i + ■ ■ ■ + ^-1 

(2,(2 + ^3, ,^, + .-■ + /,_i, - /, 

/, , /3 + /.. ,/;>+■■■+ ^-1 , -t'l ,-(/! + ^2) 



/,-! , -t^-2 , -ii.-^ + '/-2), , -(^1 + ■ • ■ + ti-2) 

-U-,, -(/,^. + ^-i). , -(/2+ ■■• +U-l), 

-((1+ ■■■ -l-/,-l). 

If the integers in each row are reduced modulo i, they will be a per- 
mutation of the integers 1, 2, -■•,«- 1. Weprovcthis by .showing that 
the opposite conclusion leads to a contradiction. If two integers in a row 

are both equal to the same integer mod i, then their difference is equal 
t,o mod i. But their dilTerence is contained elsewhere in the matrix, 
which contradicts the assumption that no starting times are mod i 
[restriction (b) aliove]. Since \vc have proved that each row is a per- 
mutation of the first [i - 1) integers, it is (^ear that the matrix con- 
sists of i starting tunes equal to a(mod t), a = 1, 2, • • • , (z - 1). 



988 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 

It is not too difficult to actually fiiid security codes satisfying restric- 
tion (b). For example, consider the security code (h = 1, (2 ^ 2, ty = 8). 
We have 

±ti= ±1 = 1 mod 4, 3 mod 4; 

±^2 =±2 = 2 mod 4, 2 mod 4; 

i/a = d=3 = 3 mod 4, I mod 4; 

±(/i + h) = ztd = 3 mod 4, 1 mod 4; 

±(^2 + /s) = ±5 - 1 mod 4, 3 mod 4; 

±(^1 + ^2 + /a) = ±6 = 2 mod 4, 2 mod 4. 

There are exactly four starting times for each of the three values of a. 
Note that this security code does not satisfy restriction (a), but that 
(/, = 1, ij = 2 + 4 = 6, /, - 3) does. 

If i < j m an i \ j two-stage code, the above two restrictions on the 
construction of security codes should be applied. However, if i > j, 
then we automatically have more than the minimum protection 
i(j — 1) — 1 against false pulses — the false command can contain at 
most ij — j false pulses (ignoring the one exception mentioned above). 
One can trade off this unnecessary additional protection for a larger set 
of security codes. To be specific, one can replace the first restriction 
with (me of the following less stringent restrictions: 

(a') no set of (i — k) false pulses, for fc = 3, 4, • • ■ , z — 1, can com- 
bine with k true pulses to form a false security code. 

These single-stage codes have already been discussed m Section II. 
For example, if one wishes to construct a 4 | 2 code, then one can u.se 
security codes that protect against only one false pulse (instead of two, 
the greatest possible protection). 

3.4 Some Typical Interleaved Security and Command Codes 

The preceding section presented two restrictions on the security code, 
which guarantee that the resultuig i \j interleaved two-stage code will 
be protected against i(j — 1 ) — 1 false pulses forming a false command. 
Nothing, however, was said about the actual construction of such codes. 
This section presents sample codes for low values of i and j. 

The command codes of an i [ j code are restricted to the spacings i, 
2i, Si, ■ • ■ and are constructed according to the methods discussed in 
Section II. The security codes are constructed by trial-and-error methods 
to satisfy the two restrictions. For i = 2, the odd integers all form se- 



MISSILE Gl'IDAXCE CODES 989 

curity encodings. For i = 3, the pairs (1, 4), (2, 5), (4, 7), (5, 8), ■ ■ ■ 
and their reverses arc legitmiate security encodings. In general, such 
encodings must be of the form ((, , /a), where h ^ h and {h , h) equals 
(1 mod 3, 1 mod 3) or (2 mod 3, 2 mod 3). For i = 4, the triples (1, 
5, 9), (2, 1, 6), (1, 6, 3), (2, 3, 6) and (6, 5, 2) are examples of short 
security encodmgs. In general, these security encodings must be of the 
form (ii , h , h) where none of the integers ^ , (2 , ^3 > ^ + '2 , '2 + (3 are 
equal, and {h , (2 , k) is in one of the foUowhig forms: (1 mod 4, 1 mod 
4, 1 mod 4); (2 mod 4, 1 mod 4, 2 mod 4); (1 mod 4, 2 mod 4, 3 mod 
4) ; (2 mod 4, 3 mod 4, 2 mod 4) ; (3 mod 4, 3 mod 4, 3 mod 4) or (3 
mod 4, 2 mod 4, 1 mod 4). 

These interleaved two-stage codes can be regarded as mmimum-length 
codes in the following sense : given that the command codes are restricted 
to the mtegers/(0, 2J{i), Zf{i), ■■■ , then 

(a) /(?■) is equal to its minimum value i; 

(b) the longest command code is as short as possible; and 

(c) the security codes are as short as possible. 

Assuming that one wishes to protect against a given number of false 
pulses, which i | j code should one select? The answer depends upon the 
relative importance of mmimizing the number of pulses ij in the code, 
and keeping the longest command delay line as short as possible. There 
are two possible ways to balance tliese factors agamst each other: 

(a) apply the methods used in one-stage codes (Section II) to the 
command code ; 

(b) change the values of both i and j; codes with large i and small j 
have shorter delay lines and more pulses, while codes with small i and 
large J have the opposite characteristics. 

Let us illustrate these ideas with a few simple examples. Assume that 
we wish to transmit six commands. The 2 | 3 and 4 | 2 codes both provide 
protection against at most three false pulses. The number of pulses per 
command is sk and eight, while the maximum delay-line length is 
19(2) = 38 and 6(4) = 24, respectively. Suppose that one uses a 2 | 4 
code but designs the command code so that it is mvulnerable to one 
false input pulse (no matter how placed) but not two. Then, referring to 
Section II, we see that the number of pulses per command is eight and 
the maximum delay line is 8(2) = 16. 

How do two-stage codes compare with one-stage codes? The only direct 
comparison available is the 2 ) 2 code with the four-pulse one-stage code 
protected against one false pulse: both codes have the same number of 
pulses and the same protection against false pulses. The length of the 
longest delay line needed is tabled below for various commands: 



990 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1 9C0 



Number of commandB 


2 


3 


4 


5 


6 


7 


Two-stage code 
One-stage code 


4 
5 


6 
6 


8 

7 


10 

8 


12 

S 


14 

9 



IV. ACKNOWLEDGMENT 



The author is indebted to W. J. Albersheim for the suggestion that a 
general study of missile codes be made. He is also indebted to W. L. 
Roach for a very careful reading of an earlier draft; his suggestions led 
to many improvements in this paper. 

APPENDIX 

Relationship to Error-Correcting Binary Codes 

There is a certain relationship between the missile guidance one-stage 
code problem presented in Section II of this paper and the error -correct- 
ing binary codes that have been extensively studied in information 
theory. Suppose that one wishes to transmit any one of a large set of 
messages over a binary channel, and .suppose that there is a pi'obability 
p that a one will be changed to a zero or a zero to a one in the course of 
transmission. One can encode the messages ui such a way that every 
message differs from every other message in at least four places: for 
example, 100000, 011100, 111 Oil and 000111. (If four messages are to be 
sent, these are the shortest messages possible.) Note that single errors 
can be corrected immediately (111111 must be 111011), and double 
errors can be detected but not corrected (110100 can be either 100000 
or 01 1100). 

In general, one attempts to encode A'^ messages in lengths as short as 
possilile so that n simultaneous errors in the encoding can be corrected 
(that is, the original message can be identified). Viewed geometrically, 
each encoded message has a cluster of closely related correctable mes- 
sages associated with it (for example, all messages differing from the 
correct one in only one unit). These clusters are packed as tightly as 
possible into a binary /i -dimensional space (/*■ is the encoded message 
length) having a total of 2*" points. When the encoded messages are 
transmitted, synchronization of some sort must be provided between 
the transmitter and the receiver in order that the receiver may know 
when each bhuuy message starts. The message length is kept as short as 
possible in order to maximize the infcjrmation rate in the chaimel.* 

The missile guidance one-stage codes of this paper can very easily 

* For a detailed discUBsion of these error-correcting binary codes, see Slepian.' 



MISSILE GUIDANCE CODES 991 

be repre.sentcd as binary messages: each binary digit corresponds to - 
time units, and the pulses of the message are represented by ones. For 
example, the two three-pulse commands (1, C) and (2, 3) become 
(11000001) and (101001). To make the representation more precise, 
the shorter messages can be extended with zeros so that all messages are 
of equal length. 

There are two differences between the missile guidance single-stage 
codes and the error-correctmg binary codes; both are discussed in the 
])aragraphs below. The first difference is concerned with synchronization, 
and the second with the shapes of the clusters of correctable messages. 

A.i Synchronization 

The error-correcting binary decoder accepts messages in non-over- 
lapping sets of k digits each ( where /; is the message length ) . This implies 
that some sort of synchronization between the sender and receiver has 
been established; otherwise the receiver does not Icnow when to start 
decoding. This synchronization is not easy to provide in missile com- 
munications, because of the rapidly changing position of the missile 
relative to the ground transmitter. Therefore, the missile receiver is 
arranged to start decoding any time a pulse (that is, a "one") is re- 
ceived. 

Some work has been done on self-synchronized codes. For example, 
Golomb, Ciordon and Welch" have derived upper bounds for the number 
of /c-digit messages that can be constructed using an /i-digit alphabet. 
They reriuire that the set of messages have the property that the final 
(A- - i) digits of any message in the set followed by the first i digits of 
any message in the set does not form a message in the set. A set of mes- 
sages with this property automatically provides synchronization; even 
when the decoder looks at all the intermediate "messages", it recognizes 
none of them. However, the work described above has not yet been ap- 
plied to errnr-correcting codes. It is possible, in fact, that self-synchro- 
nized error-cori-ecting binary codes may be of limited interest to hiforma- 
tion theorists because of the reduction hi the number of messages per 
second that can be sent over a channel. However, channel capacity and 
rate of information flow are not objectives of the missile guidance codes. 

A. 2 Clusters of Correctable Errors 

The second difference between the missile codes and Ihe binary codes 
is the shape of the cluster of correctable errors associated with a given 
message. The binary code cluster usually consists of those t-digit mes- 



992 



THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 



sages that differ in only a few digits (say, one or two) from the true 
message. The missile code cluster, on the other hand, is neither "close" 
to the true message nor easy to describe geometrically. It consists of all 
A;-digit messages that contain ones in n specified places; for example, if 
100101 is the message, then 111101, 101101 and 111111 will be decoded 
as the message. Obviously, the correctable clusters of different messages 
overlap each other. To separate the clusters as much as possible, the 
messages are selected so that no member of one cluster with (2n — 2) 
or fewer ones is a member of any other cluster. [This is simply a restate- 
ment of the requirement that (?i — 2) false pulses added to any command 
cannot possibly form a false connnand.] 

In order to visualize these correctable clusters, it is convenient to 
transform from the A;-dimonsional discrete binary space of messages to 
the (n — 1) -dimensional continuous space of times between any set of 
n pulses (true or otherwise). Let us examine the shape of this cluster a 
little more precisely for n equal to low values. For n = 2, the cluster is a 
line segment 2r units long* centered on the correct spacing ti . For ti = 3, 
the set of three-pulse messages that will be decoded as a command 
(ti , tz) is contained in the polygon of Fig. 6. This figure corresponds to a 
delay line that delays the first pulse for a time h -\- (2 , the second pulse 
for a time ^2 , and the third pulse not at all. A set of pulses with original 
spacing (ti , (») will be brought into exact coincidence by this delay line. 
The upper right corner of the square has been sawed off because, for 
original spacings (ti , (2) in this region, /i + ^2 > ^x + ^2 + t, and there- 
fore the first and third pulses will be separated by more than t after 
passing through the delay line. 

For n = 4, all decodable messages are contained in the three-dimen- 



■r — r — *] 



■^t, 




U\ti 



Fig. 6 — Polygon containing set of three-pulse messageB that will be decoded 
as a command (d , (a). 

* The quantity t is the discrete command tolerance defined in Section I. In 
order for a command to be recognized, the time between the earliest and latest of 
the n pulses arriving at the and gate must be less than t. 



MISSILE GUIDANCE CODES 



993 




Fig. 7 — Polytope containing all decodable messages for n == 4. 



sional polytope of Fig. 7. This figure corresponds to a delay line that de- 
lays the first pulse h -\- (2 -\- h , the second pulse tz + h , the third pulse 
ti , and the fourth pulse not at all. 

For 7i ^ 4, it can be shown that these polytopcs can be packed in 
such a way as to fill the space completely; it is probably not difficult to 
show that this is true for arbitrary n. The ratio of the volume of the 
(n — 1) -dimensional polytope to the (n — 1) -dimensional hypercube 
of side 2t (which encloses it) is 



[ n(n - Dx^-'d - .r) dx = 

Jo 



n + 1 

2" 



This integral is equal to the probability that n points drawn at random 
from a uniform distribution on (0, 1 ) will all be located within one-half 
of each other. 

To what use can these polytopes be put? In the bmary code problem, 
one places a message at the center of each polytope and packs them into 
the space as tightly as possible. However, in the missile guidance prob- 
lem the messages cannot be packed so closely. Consider an n-pulse com- 
mand plus (n ~ 2) false pulses. There are {2n - 2)\/n\{n - 2)! possi- 
ble ways of choosing an n-pulse group, and none of these groups (except 
for the one consisting of n true pulses) is allowed to lie withhi any poly- 
tope centered on a true command. The polytopes must be very sparsely 
scattered through (n — 1) -space. 

Let us assume that the true commands are transmitted with timing 
errors that are very small with respect to the discrete command toler- 
ance T. (This is ordinarily true in practice; if it were not, some of the 
commands might not be received by the missile.) Then, if the true com- 



994 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 

mands are encoded according to the niles stated in Section II, any false 
command consisting of (n — 2) or fewer false pulses will have at least 
one spacing Ihat is at least r dilTcrcnt from any true ciimmand spacing. 
But the polytope centered on ajiy true command is bounded by the 
hypcreulse of side 2r; therefore the false command cannot be decoded as 
any true command. In general, if the maximum timing error is e, the 
commands should be encoded in uitegral multiples of a liasic time- 
quantum T + e. 

It is not possible to relax the eneodmg rules of Section II to allow for 
the fact that we arc dealing with polytopes rather than hypercubes. The 
reason for this is simple: the polytope intersects each of the 2''"~" faces 
of the hypercube. 

REFERENCES 

1. Slepiim, D., A Class of Binary Signaling Alphabets, B.S.T.J., 35, 1956, p. 203. 

2. Golomli, S, W., Gordon, B. and Welch, L. P., Comma-Free Codes, Can. J. 

Math., 10, 1958, p, 202.